Giám mục Nguyễn Bình Tĩnh sinh ngày 30 tháng 6 năm 1930 tại giáo xứ Phát Diệm, thuộc Giáo phận Phát Diệm (thuộc địa bàn xã Lưu Phương, huyện Kim Sơn, tỉnh Ninh Bình ngày nay).[6] Song thân ông là ông Phêrô Nguyễn Văn Thừa và bà Maria Nguyễn Thị Nhiên. Nguyễn Bình Tĩnh là người con út trong gia đình.[6] Tên thánh của ông được đặt theo Thánh tử đạo Phaolô Lê Bảo Tịnh.

Thuở nhỏ, ông theo học tại Tiểu Chủng viện Ba Làng (thuộc phường Hải Thanh, Nghi Sơn, Thanh Hóa). Sau Hiệp định Genève, 1954, gia đình ông di cư vào Nam, ông được gửi theo học tại các Đại chủng viện Vĩnh Long và Đại Chủng viện Thị Nghè, do các linh mục Xuân Bích giảng dạy.[7]

Ngày 31 tháng 5 năm 1960, Nguyễn Bình Tĩnh được thụ phong linh mục, do Giám mục Simon Hòa Nguyễn Văn Hiền chủ phong.[6] Ông là linh mục thuộc linh mục đoàn giáo phận Kon Tum.[8] Sau khi thụ phong, ngày 13 tháng 6 năm 1961, ông gia nhập Tu hội Xuân Bích (tiếng Latinh: Societas Presbyterorum a S. Sulpitio), làm công tác huấn luyện đào tạo chủng sinh. Linh mục Nguyễn Bình Tĩnh được cử đi du hoc tại Đại học Công giáo Paris. Sau khi tốt nghiệp, ông trở về Việt Nam và được bổ nhiệm làm giáo sư Đại Chủng viện Xuân Bích Nha Trang và Huế.[7]

Năm 1970, linh mục Phaolô Tịnh Tĩnh được chọn làm Giám đốc Tiểu Chủng viện Thánh Gioan, Đà Nẵng. Năm 1987, ông thôi giữ chức vụ Giám đốc Tiểu chủng viện, trở thành linh mục quản xứ Giáo xứ An Hải đến năm 1994. Năm 1994, ông được chọn làm Giám đốc Đại Chủng viện Xuân Bích Huế và đã giữ chức vụ này đến khi được chọn làm Giám mục.[6][7] Ngoài ra, ông còn là linh mục Chủ tịch Hội đồng Linh mục Giáo phận Đà Nẵng, Tổng Đại diện giáo phận Đà Nẵng và là thành viên Ban Cố vấn giáo phận.[9]

Trong thời gian linh mục, linh mục Nguyễn Bình Tĩnh từng đóng vai trò trợ phong trong nghi thức truyền chức giám mục Phanxicô Xaviê Nguyễn Quang Sách năm 1975.[8]